/**
 * 剑指 Offer 28. 对称的二叉树
 * https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/
 */
const { createTreeNode } = require('../../libs/public');

// /**
//  * @param {TreeNode} node1
//  * @param {TreeNode} node2
//  * @return {boolean}
//  */
// function dfs(node1, node2) {
//   if (!node1 && !node2) {
//     return true;
//   }
//   if (!node1 || !node2) {
//     return false;
//   }
//   if (node1.val !== node2.val) {
//     return false;
//   }
//   if (!dfs(node1.left, node2.right)) {
//     return false;
//   }
//   if (!dfs(node1.right, node2.left)) {
//     return false;
//   }
//   return true;
// }
//
// /**
//  * @param {TreeNode} root
//  * @return {boolean}
//  */
// function isSymmetric(root) {
//   if (!root) {
//     return true;
//   }
//   return dfs(root.left, root.right);
// }

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
function isSymmetric(root) {
  if (!root) {
    return true;
  }
  const queue1 = [root.left];
  const queue2 = [root.right];
  while (queue1.length) {
    const node1 = queue1.shift();
    const node2 = queue2.shift();
    if (!node1 && !node2) {
      continue;
    }
    if (!node1 || !node2) {
      return false;
    }
    if (node1.val !== node2.val) {
      return false;
    }
    queue1.push(node1.left, node1.right);
    queue2.push(node2.right, node2.left);
  }
  return true;
}

console.log(isSymmetric(createTreeNode([1, 2, 2, 3, 4, 4, 3])) === true);
console.log(isSymmetric(createTreeNode([1, 2, 2, null, 3, null, 3])) === false);
